public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;

        int[] sub = new int[len];

        for (int i = 0; i < len; i++) {
            sub[i] = gas[i] - cost[i];
        }

        for (int i = 0; i < len; i++) {
            int count = 0;
            int sum = 0;
            while (count < len) {
                sum += sub[(i + count) % len];
                if (sum < 0) {
                    break;
                }
                count++;
            }
            if (sum >= 0) {
                return i;
            }
        }

        return -1;
    }

    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int len = gas.length;

        int[] sub = new int[len];

        for (int i = 0; i < len; i++) {
            sub[i] = gas[i] - cost[i];
        }

        for (int i = 0; i < len; i++) {
            int count = 0;
            int sum = 0;
            while (count < len) {//从i位置开始计算，会多计算一个count
                sum += sub[(i + count) % len];
                count++;
                if (sum < 0) {
                    break;
                }
            }
            if (sum >= 0) {
                return i;
            } else {
                i += (count - 1);
            }
        }

        return -1;
    }
}
